1. Field of the Invention
This invention relates generally to network management and specifically relates to controlling traffic flow in network devices.
2. Description of Related Art
In digital communications systems, data are transmitted between processing devices over a network. In such networks, data are typically sent from one computer to another through network devices such as hubs, routers, bridges and/or switches interconnected by data links.
Network devices have ports that send and receive data, commands, etc. (hereinafter, “data”) to and from the data links. Although this disclosure will mainly refer to data sent in the form of packets, the present invention applies to any addressable entities, including but not limited to datagrams, cells, etc. Accordingly, the terms “packet,” “frame,” “cell,” etc., will be used synonymously herein.
Within a single network device, packets are accepted at ingress ports, transferred across a switching fabric within the network device and received at egress ports for transmission over the next data link. If each input port maintains a single first-in, first-out (“FIFO”) buffer or “queue,” various difficulties can arise,
FIG. 1 illustrates one such difficulty, known as head-of-line (“HOL”) blocking. In this example of HOL blocking, more than one ingress port has a packet at the head of its queue that is destined for the same egress port at the same time. Ingress port 105 has a single queue 106, where incoming packets are stored until they are routed to an appropriate egress port. Similarly, ingress ports 110 and 115 have corresponding queues 111 and 116.
Suppose port 125 is not accepting packets, whereas ports 120 and 130 are free. Queue 116 has packets bound for port 130 and port 120, so these packets can be sent in sequence. However, queues 106 and 111 both have packets at the head of the line that need to be routed to egress port 125. The second packet in queue 106 needs to egress port 120 and the second packet in queue 111 needs to egress port 130. Even though ports 120 and 130 are free, the second packets in queues 106 and 111 will be blocked, because the HOL packets in each queue cannot be sent. Even if port 125 were accepting packets for egress, there would be contention between queues 106 and 111 for sending their HOL packets to port 125. This contention would need to be resolved before the next packets could be sent.
To eliminate HOL blocking, virtual output queues (VOQs) have been proposed. In VOQ implementations, ingress ports have a bank of queues, with one queue per category. Categories may include, for example, source, destination and priority. Packets are stored in random access buffers associated with the ingress ports. However, only pointers to the data need to be stored in the respective VOQs; the payloads may be stored elsewhere (e.g., in an off-chip random access memory).
In conventional VOQ implementations, the number of necessary queues needs to equal at least the total number of possible categories. As the number of categories increases, however, such implementations are not practical. For example, suppose a switch has 1024 ports and each ingress port has VOQs that include the categories of source, destination and priority. If each packet could have any one of 1024 destinations, 1024 sources and 4 levels of priority, over 4 million queues would be required for routing packets within the switch. If the queues are implemented as physical memories on a chip, over 4 million physical memories would be required.
This problem is exacerbated when one considers the high data transfer rates of recently-developed network devices. If a switch has, for example, 1000 ingress/egress ports transferring packets at 2 G/s, there are 1000 2 G/s data streams to manage. If the data structure to be managed has over 4 million entities to manage in a picosecond time frame, this is not a feasible management problem for hardware that will be available in the foreseeable future. Accordingly, it would be desirable to have improved methods of switching packets within network devices.